package algorithm.leetcode.I101to200;

/**
 * 参考 Q123,相似度99%
 */

// 上一轮:[    买1,  买1卖1,    买2卖1,...买k卖K-1, 买k卖K], price[i]
//             \       |\       |         \       |
//              \      | \      |          \      |
//               \+    |  \-    |           \+    |
//                \p[i]|   \p[i]|            \p[i]|
//                 \   |    \   |             \   |
//                  \  |     \  |              \  |
//                   \ |max   \ |max            \ |max
// 在本轮:[0-price[i], 买1卖1, 买2卖1,...买k卖K-1, 买k卖K]

public class Q188 {

    public int maxProfit(int k, int[] prices) {
        if (prices.length < 2 || k == 0) return 0;

        int maxProfit = Integer.MIN_VALUE;
        // dp数组每个位置的含义是 [买1, 买1卖1,买2卖1,...,买k卖K] 行为的收益
        int[] dp = new int[2*k];
        // 初始化dp数组,只要买入大于卖出,就是-prices[0]
        for (int i = 0; i < k; i++) {
            dp[2*i] = -prices[0];
        }

        for (int i = 1; i < prices.length; i++) {
            int[] clone = dp.clone();
            dp = new int[2*k];

            for (int j = 0; j < dp.length; j++) {
                if (j == 0) dp[j] = Math.max(-prices[i], clone[j]);
                else {
                    // 奇数索引执行卖出,偶数索引执行买入
                    int todayIn = (j&1) == 1 ? prices[i] : -prices[i];
                    dp[j] = Math.max(clone[j], clone[j-1] + todayIn);
                }
                maxProfit = Math.max(maxProfit, dp[j]);
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        Q188 q188 = new Q188();
        System.out.println(q188.maxProfit(2, new int[]{2, 4, 1}));
    }
}
